#include <stdio.h>

//#define NUM 17
#define NUM 7


/*
 * about quck sort 
 */
int partition(int data[], int low, int high)
{
	int i = low, j = high;
	int pivot = data[i];
	while (i < j) {
		while (i < j && data[j] >= pivot)
			j--;
		if(i < j) {
			data[i] = data[j];
			i++;
		}

		while(i < j && data[i] <=  pivot)
			i++;
		if (i < j) {
			data[j] = data[i];
			j--;
		}
	}
	data[i] = pivot;

	{
		int k = 0;
		for (k = 0; k < NUM; k++)
			printf("%d  ", data[k]);
		printf("\n");
	}

	return i;
}

void quick_sort(int data[], int low, int high)
{
	int part_pos;
	part_pos = partition(data, low, high);
	if (low < high - 1) 
		quick_sort(data, low, part_pos - 1);
	if (part_pos + 1 < high) 
		quick_sort(data, part_pos + 1, high);
}

void swap(int data[], int i, int j)
{
	int t = 0;
	t = data[i];
	data[i] = data[j];
	data[j] = t;
}

void quick_sort2(int data[], int low, int high)
{
	int i, m, tmp;
	if (low >= high)
		return;
	m = low;

	for (i = low + 1; i <= high; i++)
		if (data[i] < data[low])
			swap(data, ++m, i);
	swap(data, low, m);
	quick_sort2(data, low, m - 1);
	quick_sort2(data, m + 1, high);
			
	
}

/*
 * about bubble sort
 */

void bubble_sort(int data[], int num)
{
	int i, j, tmp;
	for(i = 0; i < num; i++) {
		for (j = 1; j < num -i; j++) {
			if (data[j -1] <= data[j])
				continue;
			tmp = data[j];
			data[j] = data[j-1];
			data[j-1] = tmp;
		}
	}
}

/*
 * about heap sort
 */
void siftup(int data[], int i)
{
	int p, tmp;
	
	printf("siftup::i:%d\n", i);
	while (i > 0) {
		p = (i - 1) / 2;
		if (data[i] < data[p]) {
			tmp = data[i];
			data[i] = data[p];
			data[p] = tmp;
		}
		i = p;
	}
}

void siftdown(int data[], int n)
{
	int p = 0, r, tmp;

	printf("siftdown::n:%d\n", n);
	while (p < n) {
		r = (p + 1) << 1;
		if (r - 1 > n - 1)
			break;
		if ( r <= n -1 && data[r - 1] > data[r])
			r--;
		if (data[p] > data[r]) {
			tmp = data[r];
			data[r] = data[p];
			data[p] = tmp;
		}
		p = r;
	}
}

/* @n: the num of data in data[] */
void heap_sort(int data[], int n)
{
	int i, tmp, j;
	for(i=1; i < n; i++)
		siftup(data, i);

	for (i = 0; i < NUM; i++)
		printf("%d  ", data[i]);
	printf("\n");

	for(i = n - 1; i > 0; i--) {
		tmp = data[0];
		data[0] = data[i];
		data[i] = tmp;
		siftdown(data, i);
		for (j = 0; j < NUM; j++)
			printf("%d  ", data[j]);
		printf("\n");
	}
}

int main () 
{
	//int data[NUM] = {6, 9, 7, 8, 0, 19, 12, 16, 13, 11, 18, 14, 1, 3, 2, 5, 4};
	int data[NUM] = {6, 9, 7, 8, 0, 19, 4};
	int i;

//	quick_sort(data, 0, NUM - 1);
//	bubble_sort(data, NUM);
//	quick_sort2(data, 0, NUM - 1);
	heap_sort(data, NUM);

	for (i = 0; i < NUM; i++)
		printf("%d  ", data[i]);
	printf("\n");

	return 0;
}

